/** \file    listsort.h
  * \brief   Sorting of std::list without limitation on maximum elements in list (M$ - 2^15).
  * \date    2001
  * \author  Fedor Chelnokov
  * \version $Header: /home/cscom1r4/cvsroot/cs/include/xtd/listsort.h,v 1.1 2004/12/02 23:53:11 cscom1r4 Exp $
  */

#ifndef _listsort_h_
#define _listsort_h_

#include <list>

namespace xtd {

template<class _Ty, class _A >
void listsort( std::list<_Ty,_A> &l )
{
	typedef std::list<_Ty,_A> _Myt;
	if (2 <= l.size()) {
		const size_t _MAXN = 32;
		_Myt _X, _A[_MAXN + 1];
		size_t _N = 0;
		while (!l.empty())
			{_X.splice(_X.begin(), l, l.begin());
			size_t _I;
			for (_I = 0; _I < _N && !_A[_I].empty(); ++_I)
				{_A[_I].merge(_X);
				_A[_I].swap(_X); }
			if (_I == _MAXN)
				_A[_I].merge(_X);
			else
				{_A[_I].swap(_X);
				if (_I == _N)
					++_N; }}
		while (0 < _N)
			l.merge(_A[--_N]); 
	}
}


}

#endif //_listsort_h_
